#include<stdio.h>
#include<stdlib.h>
/**
*  Tutorial #10 (Merge and Quick Sort)
*  Program to Merge Sort
**/
int main4(){
    printf("Enter the value of n\n");
    int n,i;
    scanf("%d",&n);
    int ar[n];
    printf("Enter the values");
    for(i = 0;i<n;i++){
        scanf("%d",&ar[i]);
    }
    mergeSort(ar,0,n-1);
    printf("The sorted values are\n");
    for(i=0;i<n;i++){
        printf("%d",ar[i]);
    }
}

void mergeSort(int ar[],int i,int j){
    if(i >= j){
        return;
    }else{
        int mid = (i+j)/2;
        mergeSort(ar,i,mid);
        mergeSort(ar,mid+1,j);
        merge(ar,i,j,mid);
    }
}

void merge(int ar[],int i,int j,int mid){
    int arr[j+1],index = i;
    int m = i,n= mid+1;
    while(m <= mid && n<= j){
        if(ar[m] <= ar[n]){
            arr[index] = ar[m];
            m++;
            index++;
        }else{
            arr[index] = ar[n];
            n++;
            index++;
        }
    }
    if(m > mid){
        while( n <= j){
            arr[index] = ar[n];
            index++;
            n++;
        }
    }else{
        while (m <= mid){
            arr[index] = ar[m];
            index++;
            m++;
        }
    }
    while(i <=j){
        ar[i] = arr[i];
        i++;
    }
}
